package ljl.alg.jianzhioffer.round2;

import java.util.ArrayList;
import java.util.List;

/**
 * 这个比较新颖，是从 1 开始到 target
 * 连续的序列， 至少两个数
 * 必须是连续的！
 *
 * 输出所有可能的序列
 * */
public class _57_s_sum_continuous {
    
    // 必须连续，是不是最大值也就是 target / 2 + 1 了？
    
    static class timeout {
        /*
         * 我思路是构造一个和序列，然后挨个做差试试？不行吧
         * */
        /**
         * 这个解法本身是对的，但是会超时！
         * */
        public static int[][] findContinuousSequence(int target) {
            List<int[]> res = new ArrayList<>();
            int r = target / 2 + 1;
            // 0 1 3 6 10 ...
            int[] sumArr = new int[r + 1];
            for (int i = 1; i <= r; i++) {
                sumArr[i] = sumArr[i - 1] + i;
            }
            for (int i = 1; i <= r; i++) {
                if (sumArr[i] < target)
                    continue;
                for (int j = 0; j < i; j++) {
                    int diff = sumArr[i] - target;
                    if (sumArr[j] == sumArr[i] - target) {
                        int[] each = new int[i - j];
                        for (int k = 0; k < each.length; k++) {
                            each[k] = j + k + 1;
                        }
                        res.add(each);
                        // 如果差值比 diff 大了，以后会越来越大更不可能相等了
                    } else if (diff < sumArr[j])
                        break;
                }
            }
            return res.toArray(new int[0][]);
        }
    }
    
    // 解方程组
    /*
    * 这个解法不太讨喜，不过也是一种解法
    * target = (j - i + 1)(i + j)/2
    *        = ij + j2 - i2 - ij + i + j
    * j2 + j - i2 + i - 2target = 0
    * i =  -1 + 根号下 1 + 4(i2 - i + 2target)，再除以 2
    * 意思是，target 等于区间长度乘以平均值，很简单吧，然后固定 i 解 j
    * 当 j 是个 int 时就是其中一个解
    * 然后不停的移动 i，直到 i == j
    *
    * 其实这个解还挺短小精悍的！
    * */
    public static int[][] findContinuousSequence0(int target) {
        int i = 1;
        double j = 2.0;
        List<int[]> list = new ArrayList<>();
        while (i < j) {
            j = (Math.sqrt(1 + 4 * ((long)i * i - i + 2L * target)) - 1) / 2;
            if (i < j && j == (int)j) {
                int[] group = new int[(int) (j - i + 1)];
                for (int k = i; k <= j; k++) {
                    group[k - i] = k;
                }
                list.add(group);
            }
            i++;
        }
        return list.toArray(new int[0][]);
    }
    
    
    /**
     * 我感觉很难啊，初始值想不到
     * 哪有那么简单！
     * */
    public static int[][] findContinuousSequence1(int target) {
        // 注意这里，初始化
        int i = 1, j = 2, s = 3;
        List<int[]> list = new ArrayList<>();
        while (i < j) {
            if (s == target) {
                int[] group = new int[j - i + 1];
                for (int k = i; k <= j; k++) {
                    group[k - i] = k;
                }
                list.add(group);
            }
            // 注意这里
            if (s <= target)
                s += ++j;
            else
                s -= i++;
        }
        return list.toArray(new int[0][]);
    }
    
}
